public class Solution437 {

    int[] sum=new int[1005];
    int ans;

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int pathSum(TreeNode root, int targetSum) {
        search(root,targetSum,1);
        return ans;
    }

    public void search(TreeNode root,int targetSum,int deep){
        if (root==null) return;
        sum[deep]=sum[deep-1]+root.val;
        for (int i=0;i<deep;i++){
            if (sum[deep]-sum[i]==targetSum){
                ans++;
            }
        }
        search(root.left,targetSum,deep+1);
        search(root.right,targetSum,deep+1);
    }

    public static void main(String[] args) {
        TreeNode t3=new TreeNode(3,new TreeNode(3),new TreeNode(-2));
        TreeNode t2=new TreeNode(2,null,new TreeNode(1));
        TreeNode t5=new TreeNode(5,t3,t2);
        TreeNode tm3=new TreeNode(-3,null,new TreeNode(11));
        TreeNode t10=new TreeNode(10,t5,tm3);
        System.out.println(new Solution437().pathSum(t10,8));
    }
}
